一道很不错的树形dp。
令 为以为根的子树。
,表示为服务器,那么的儿子和父亲既可以是服务器,也可以不是。
,表示的父亲为服务器,那么的儿子一定不为服务器。
,表示和的父亲均不为服务器,那么的儿子中一定有一个是服务器。
那么转移式为:
其中 为 的子结点个数 , 是枚举的为服务器的那个子节点。
这样转移需要 , 经过观察发现,求和的部分与 除了枚举的 是一致的 , 于是就可以化简为:
最后注意的极大值,用 可能会爆 , 开成 即可。
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 10000;
int n , u , v , dp[ MAXN + 5 ][ 3 ];
vector< int > Graph[ MAXN + 5 ];
void dfs( int u , int fa ) {
dp[ u ][ 0 ] = 1; dp[ u ][ 1 ] = 0;
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
int v = Graph[ u ][ i ];
if( v == fa ) continue;
dfs( v , u );
dp[ u ][ 0 ] += min( dp[ v ][ 0 ] , dp[ v ][ 1 ] );
dp[ u ][ 1 ] += dp[ v ][ 2 ];
dp[ u ][ 2 ] = min( dp[ u ][ 2 ] , dp[ u ][ 1 ] - dp[ v ][ 2 ] + dp[ v ][ 0 ] );
}
}
int main( ) {
while( scanf("%d",&n) ) {
for( int i = 1 ; i <= n ; i ++ ) {
Graph[ i ].clear( );
dp[ i ][ 0 ] = dp[ i ][ 1 ] = dp[ i ][ 2 ] = MAXN;
}
for( int i = 1 ; i <= n - 1 ; i ++ ) {
scanf("%d %d",&u,&v);
Graph[ u ].push_back( v );
Graph[ v ].push_back( u );
}
dfs( 1 , 0 );
printf("%d\n", min( dp[ 1 ][ 0 ] , dp[ 1 ][ 2 ] ) );
scanf("%d",&n);
if( n == -1 ) break;
}
return 0;
}